package com.lagou.bak.base;

public class QuickSort {
    public static void main(String[] args) {
        int[] arrs = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
        sortQuit(arrs, 0, arrs.length-1);
        for (int i = 0; i < arrs.length; i++) {
            System.out.print(arrs[i] + " ");
        }
    }

    static void sortQuit(int[] arrs,int left, int right) {
        if (left > right) {
            return;
        }
        int base = arrs[left];
        int i = left;
        int j = right;
        while(i < j) {
            //从右边开始找比base小的
            while(base <= arrs[j] && i < j) {
                j--;
            }
            //从左边开始找比base大的
            while(base >= arrs[i] && i < j) {
                i++;
            }
            if(i < j) {
                int t = arrs[j];
                arrs[j] = arrs[i];
                arrs[i] = t;
            }
        }
        arrs[left] = arrs[i];
        arrs[i] = base;
        sortQuit(arrs, left, j-1);
        sortQuit(arrs, j+1, right);
    }
}
